#pragma once
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctime>
#include <utility>
#include <cstdlib>
template<typename Comparable>
class BinarySearchTree
{
public:
	BinarySearchTree(){
		this->root = NULL;
		this->size = 0;
	}
	BinarySearchTree(const BinarySearchTree& rhs);

	const Comparable findMin() const;
	const Comparable findMax() const;
	bool contains(const Comparable& x)const;
	bool isEmpty() const;
	void printTree() const;

	void insert(const Comparable& x);
	void remove(const Comparable& x);
    void makeEmpty();
	const BinarySearchTree& operator=(const BinarySearchTree& rhs)
	{
		if (this != &rhs)
		{
			makeEmpty();
			root = clone(rhs.root);
		}
		return *this;
	}

	~BinarySearchTree()
	{
		makeEmpty();
	}
private:
	struct BinaryNode
	{
		Comparable element;
		BinaryNode* left;
		BinaryNode* right;

		BinaryNode(const Comparable& theElement,BinaryNode* lt,BinaryNode* rt):element(theElement),left(lt),right(rt){}
	};

	BinaryNode* root;
    int size;
	void insert(const Comparable& x, BinaryNode*& t)const;
	void remove(const Comparable& x, BinaryNode*& t)const;
	bool contains(const Comparable& x, BinaryNode* t)const;
	void printTree(BinaryNode* t)const;

	BinaryNode* findMin(BinaryNode* t) const
	{
		if (t == NULL)
			return NULL;
		else if (t->left == NULL)
			return t;
		return findMin(t->left);
	}

	BinaryNode* findMax(BinaryNode* t) const
	{
		if (t == NULL)
			return NULL;
		else if (t->right == NULL)
			return t;
		return findMax(t->right);
	}

	void insert(const Comparable& x, BinaryNode*& t)
	{
		if (t == NULL)
			t = new BinaryNode(x, NULL, NULL);
		else if (x < t->element)
			insert(x, t->left);
		else if (x > t->element)
			insert(x, t->right);
		else
			;
	}

	void remove(const Comparable& x, BinaryNode*& t)
	{
		if (t == NULL)
			return;
		if (x < t->element)
			remove(x, t->left);
		else if (x > t->element)
			remove(x, t->right);
		else if (t->left != NULL && t->right != NULL)
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			BinaryNode* oldNode = t;
			t = (t->left != NULL) ? t->left : t->right;
			delete oldNode;
		}
	}

	void makeEmpty(BinaryNode*& t)
	{
		if (t != NULL)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = NULL;
	}

	BinaryNode* clone(BinaryNode* t) const
	{
		if (t == NULL)
			return NULL;

		return new BinaryNode(t->element, clone(t->left), clone(t->right));
	}
};

template<typename Comparable>
bool BinarySearchTree<Comparable>::contains(const Comparable& x) const
{
	return contains(x, root);
}

template<typename Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable& x) 
{
	insert(x, root);
}
template<typename Comparable>
void BinarySearchTree<Comparable>::makeEmpty() 
{
	makeEmpty(root);
}
template<typename Comparable>
void BinarySearchTree<Comparable>::remove(const Comparable& x)
{
	remove(x, root);
}

template<typename Comparable>
bool BinarySearchTree<Comparable>::contains(const Comparable& x, BinaryNode* t) const
{
	if (t == NULL)
		return false;
	else if (x < t->element)
		return contains(x, t->left);
	else if (x > t->element)
		return contains(x, t->right);
	else
		return true;
}
template<typename Comparable>
const Comparable BinarySearchTree<Comparable>::findMin() const
{
	return findMin(root)->element;
}
template<typename Comparable>
const Comparable BinarySearchTree<Comparable>::findMax() const
{
	return findMax(root)->element;
}
/*template<typename Object,typename Comparator=less<Object>>
class BinarySearchTree
{
public:
	template<typename Comparable>
	friend class BinarySearchTree<Comparable>;
private:
	BinaryNode* root;
	Comparator isLessThan;

	bool contains(const Object& x, BinaryNode* t) const
	{
		if (t == NULL)
			return false;
		else if (isLessThan(x, t->element))
			return contains(x, t->left);
		else if (isLessThan(t->element, x))
			return contains(x, t->right);
		else
			return true;
	}
};*/

template<typename Comparable>
void BSTsorting(std::vector<Comparable>& _arr, int _mode = 0)
{
	BinarySearchTree<int> Tree;
	int size = _arr.size();
	if (_mode == 0) {
		for (int i = 0; i < size; i++) {
			Tree.insert(_arr[i]);
		}
		for (int i = 0; i < size; i++) {
			_arr[i] = Tree.findMin();
			Tree.remove(_arr[i]);
		}
		Tree.makeEmpty();
	}
	if (_mode == 1) {
		std::random_shuffle(_arr.begin(), _arr.end());
		for (int i = 0; i < size; i++) {
			Tree.insert(_arr[i]);
		}
		for (int i = 0; i < size; i++) {
			_arr[i] = Tree.findMin();
			Tree.remove(_arr[i]);
		}
		Tree.makeEmpty();
	}
}











